翻訳と辞書 Words near each other ・ Kerr Scott Farm ・ Kerr Smith ・ Kerr Stuart steam railmotor ・ Kerr Sulphurets Mitchell ・ Kerr Township, Champaign County, Illinois ・ Kerr Whiteside ・ Kerr's Atlantic tree-rat ・ Kerr's Building ・ Kerr's Miniature Railway ・ Kerr's noctuid moth ・ Kerr's Patent Revolver ・ Kerr's Pink ・ Kerr's sign ・ Kerr, Montana ・ Kerr, Ohio ・ Kernighan–Lin algorithm ・ Kernilis ・ Kerning ・ Kernite ・ Kernkraft 400 ・ Kernmantle rope ・ Kernmünsterland ・ Kernodle-Pickett House ・ Kernohan's notch ・ Kernohan, Edmonton ・ Kernos ・ Kernot ・ Kernot railway station ・ Kernouës ・ Kernowek Standard Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Kernighan–Lin algorithm ： ウィキペディア英語版 Kernighan–Lin algorithm : ''This article is about the heuristic algorithm for the graph partitioning problem. For a heuristic for the traveling salesperson problem, see Lin–Kernighan heuristic.'' Kernighan–Lin is a O(n2 log(n)) heuristic algorithm for solving the graph partitioning problem. The algorithm has important applications in the layout of digital circuits and components in VLSI.〔〔 ==Description== Let $G(V,E)$ be a graph, and let $V$ be the set of nodes and $E$ the set of edges. The algorithm attempts to find a partition of $V$ into two disjoint subsets $A$ and $B$ of equal size, such that the sum $T$ of the weights of the edges between nodes in $A$ and $B$ is minimized. Let $I\_$ be the ''internal cost'' of ''a'', that is, the sum of the costs of edges between ''a'' and other nodes in ''A'', and let $E\_$ be the ''external cost'' of ''a'', that is, the sum of the costs of edges between ''a'' and nodes in ''B''. Furthermore, let :$D\_\; =\; E\_\; -\; I\_$ be the difference between the external and internal costs of ''a''. If ''a'' and ''b'' are interchanged, then the reduction in cost is :$T\_\; -\; T\_\; =\; D\_\; +\; D\_\; -\; 2c\_$ where $c\_$ is the cost of the possible edge between ''a'' and ''b''. The algorithm attempts to find an optimal series of interchange operations between elements of $A$ and $B$ which maximizes $T\_\; -\; T\_$ and then executes the operations, producing a partition of the graph to ''A'' and ''B''. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Kernighan–Lin algorithm」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.